package com.fulin.leetcode;

/**
 * 将有序数组转换为二叉搜索树
 *
 * @Author fulin
 * @Date 2022/9/20 16:51
 **/
public class Num108 {

    public static void main(String[] args) {
       int[] nums = new int[]{-10,-3,0,5,9};
       sortedArrayToBST(nums);
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        return gen(nums,0,nums.length - 1);
    }

    private static TreeNode gen(int[] nums,int begin,int end){
        if(begin > end){
            return null;
        }

        //选择中间位置左边的元素作为根节点
        int mid = (end + begin) / 2;
        TreeNode left = gen(nums,begin,mid - 1);
        TreeNode right = gen(nums,mid + 1,end);
        TreeNode node = new TreeNode(nums[mid],left,right);
        return node;
    }
}
